4081. Frequent values - 2

You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j.

Input. Consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 500000). The next line contains n integers a₁ , ... , a_n (-500000 ≤ a_i ≤ 500000, for each i Î {1, ..., n}) separated by spaces. You can assume that for each i Î {1, ..., n – 1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.

The last test case is followed by a line containing a single 0.

Output. For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Sample input

10 3

-1 -1 1 1 1 1 3 10 10 10

2 3

1 10

5 10

0

Sample output

1

4

3

SOLUTION

data structures – RMQ

Анализ алгоритма

This problem differs from 3838 (Frequent values) with increasing the limits by n and q, and also the number of queries, where the solution with segment tree gives Time Limit.

As the input sequence is given at once and never changes (there is no update operation), the problem can bt solved using Range Maximum Query data structure. Its advantage is that the query on a segment runs in constant time, not in logarithmic as using the Segment Tree. So:

· time to solve the problem with Segment Tree: O(n + q log₂n).

· time to solve the problem with RMQ: O(n log₂n + q).

Note also that the memory used is:

· O(n) for Segment Tree

· O(n log₂n) for RMQ

To reduce the given problem to RMQ, using the input sequence create the new array b: b[i] contains the number of repetitions of number a_i up to index i. For example, if a = (3, 3, 5, 9, 9, 9, 9, 10, 10), then b = (1, 2, 1, 1, 2, 3, 4, 1, 2).

The anwer to the given query q(i, j) can be found with the following manner:

· if a_i = a_j, the answer is the value j – i + 1;

· otherwise find the rightmost index k, for which a_i = a_k. После чего находим максимальное значение на отрезке b[k + 1, …, j], то есть RMQ_k+1,j (для удобства вычислений Range Maximum Query будет возвращать не индекс с максимальным элементом, а сам максимальный элемент). Тогда ответом на запрос будет

max (k – i + 1, RMQ_k+1,j).

Example

Input array а:

The corresponding array b:

Consider the query q(4, 9). Then k = 6 (a₄ = a₆, a₄ ≠ a₇). The answer is

max (k – i + 1, RMQ_k+1,j) = max (6 – 4 + 1, RMQ_7,9) = max (3, 2) = 3

Consider the query q(2, 5). Then k = 2 (a₂ = a₂, a₂ ≠ a₃). The answer is

max (k – i + 1, RMQ_k+1,j) = max (2 – 2 + 1, RMQ_3,5) = max (1, 3) = 3

Реализация алгоритма

Объявим необходимые константы. Входная последовательность хранится в массиве а. Объявим вспомогательный массив b. Массив mas будет использоваться под структуру RMQ: mas[i][j] содержит максимальный элемент на отрезке [i, …, i + 2^j]. Массив mas хранит не индексы последовательности, а сами максимальные значения на отрезках. Таким образом мы избавимся от большого числа операций индексации.

#define MAX 500010

#define LOGMAX 19

int a[MAX], b[MAX];

int mas[MAX][LOGMAX];

По массиву b строим массив mas, для которого mas[i][j] = max(b_i, b_i+1, …, b_i+2^j).

void Build_RMQ_Array(int *b)

{

int i, j;

for (i = 1; i <= n; i++) mas[i][0] = b[i];

for (j = 1; 1 << j <= n; j++)

for (i = 1; i + (1 << j) - 1 <= n; i++)

if (mas[i][j - 1] > mas[i + (1 << (j - 1))][j - 1])

mas[i][j] = mas[i][j - 1];

else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];

}

Функция RMQ возвращает максимум на отрезке (b_i, b_i+1, …, b_j) за O(1).

int RMQ(int i, int j)

{

int k = (int)(log(1.0*j-i)/log(2.0));

int res = mas[i][k];

if (mas[j - (1<<k) + 1][k] > res) res = mas[j - (1<<k) + 1][k];

return res;

}

Основная часть программы. Читаем входной массив а. Одновременно строим по нему массив b.

while(scanf("%d %d",&n,&q), n)

{

scanf("%d",&a[1]); b[1] = 1;

for(i = 2; i <= n; i++)

{

scanf("%d",&a[i]);

if (a[i] == a[i-1]) b[i] = b[i-1] + 1; else b[i] = 1;

}

Строим структуру данных RMQ.

Build_RMQ_Array(b);

Последовательно обрабатываем запросы.

for(i = 0; i < q; i++)

{

scanf("%d %d",&Left,&Right);

if (a[Left] == a[Right]) printf("%d\n",Right - Left + 1);

else

{

LeftEnd равно самому правому индексу, для которого a_i = a_LeftEnd.

int LeftEnd = (int)(upper_bound(a+Left,a+Right,a[Left]) - a) - 1;

res = max(LeftEnd - Left + 1, RMQ(LeftEnd + 1, Right));

printf("%d\n",res);

}

}

}